package 链表;

import java.util.Stack;

public class No45两数相加_2 {

    /**
     * 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。
     * 它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
     * 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
     * 进阶：
     * 如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
     * 示例：
     * 输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
     * 输出：7 -> 8 -> 0 -> 7
     */

    /*
    因为是正序存储的,所以我们不可以直接从第一位相加,因为从两个链表的最底部开始相加,
    瞟了一眼题解,可以用stack这个数据结构来实现翻转
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stack1=new Stack<>();
        Stack<Integer> stack2=new Stack<>();

        while (l1!=null){
            stack1.push(l1.val);
            l1=l1.next;
        }

        while (l2!=null){
            stack2.push(l2.val);
            l2=l2.next;
        }

        ListNode listNode=new ListNode();
        ListNode head=listNode;

        int o1;
        int o2;
        int extra=0;//上一位是否有多出
        //根据No2两数相加的记忆,应该用while,两个链表一起吃,只吃存在的
        while (!stack1.empty()||!stack2.empty()){

            o1=stack1.empty()?0:stack1.pop();
            o2=stack2.empty()?0:stack2.pop();//都吐出

            int sum=o1+o2+extra;//本次的和(需要加上上一节点传来的)
            int legacy=sum%10;//留给本次节点的
            extra=sum/10;//传递给下一节点的

            ListNode thisNode=new ListNode(legacy);
            System.out.println(legacy);
            listNode.next=thisNode;
            listNode=listNode.next;
        }

        if(extra!=0){
            ListNode thisNode=new ListNode(extra);
            listNode.next=thisNode;
            listNode=listNode.next;
        }

        Stack<ListNode> stack3=new Stack<>();
        ListNode cur=head.next;
        while (cur!=null){
            stack3.push(cur);
            cur=cur.next;
        }

        ListNode result=new ListNode();
        ListNode oo=result;
        while (!stack3.empty()){//和isEmpty()没区别
            result.next= stack3.pop();
            result=result.next;
            if(stack3.empty())
                result.next=null;
        }

        return oo.next;
    }

    public static void main(String[] args) {

        int[] arr1=new int[]{7,2,4,3};
        int[] arr2=new int[]{7,5,6,4};

        ListNode listNode1=ListNode.createListNode(arr1);
        ListNode listNode2=ListNode.createListNode(arr2);

        ListNode listNode = addTwoNumbers(listNode1, listNode2);

        ListNode.printListNode(listNode);

    }

}
